package 剑指offer_力扣版.Month07.day04数组;

import java.util.HashMap;
import java.util.Map;

public class 零和一个数相同的子数组 {

    public int findMaxLength(int[] nums) {
        for(int i = 0;i < nums.length;i++) {
            if (nums[i] == 0) nums[i] = -1;
        }
        //求和为0的最长连续子数组
        Map<Integer,Integer> map = new HashMap();
        map.put(0,-1);
        int res = 0;//前缀和
        int maxlen = 0;
        for(int i = 0;i < nums.length;i++){
            res += nums[i];
            if(map.containsKey(res-0)){
                maxlen = Math.max(maxlen,i - map.get(res));
            }else{
                map.put(res,i);
            }
        }
        return maxlen;
    }

    //怨种写法，相同数量的0和1
//    public int findMaxLength(int[] nums) {
//        int[] dp = new int[nums.length];
//        dp[0] = 1;
//        int max = Integer.MIN_VALUE;
//        for(int i = 1;i < nums.length;i++){
//            if(solve(nums[i],nums[i - 1])){
//                dp[i] = dp[i - 1] + 1;
//            }else{
//                dp[i] = 1;
//            }
//            max = Math.max(max,dp[i]);
//        }
//        return max;
//    }
//
//    public boolean solve(int A,int B){
//        int countA0 = 0;
//        int countA1 = 0;
//        for (int i = 0; i < 32; i++) {
//            if(((A >> i) & 1) == 1){
//                countA1++;
//            }else{
//                countA0++;
//            }
//        }
//        int countB0 = 0;
//        int countB1 = 0;
//        for (int i = 0; i < 32; i++) {
//            if(((B >> i) & 1) == 1){
//                countB1++;
//            }else{
//                countB0++;
//            }
//        }
//        if(countA0 + countA1 == countB0 + countB1) return true;
//        return false;
//    }
}
